public class MergeSort {


    /**
     *  归并排序
     */


    int[] tmp;
    public int[] sortArray(int[] nums) {
        tmp = new int[nums.length];
        merge(nums,0,nums.length-1);
        return nums;
    }
    public void merge(int[] nums,int start,int end) {
        if(start>=end) return; //一个元素无需排序
        //1.不断递归
        int mid = (end+start)>>1;
        merge(nums,start,mid);
        merge(nums,mid+1,end);
        //2.合并该区间
        int i=start,j=mid+1,k=start;
        while(i<=mid && j<=end) {
            if(nums[i] < nums[j]) tmp[k++]=nums[i++];
            else tmp[k++]=nums[j++];
        }
        while(i<=mid) {
            tmp[k++]=nums[i++];
        }
        while(j<=end) {
            tmp[k++]=nums[j++];
        }
        //3.写回原数组
        k=start;
        while(k<=end) {
            nums[k]=tmp[k];
            k++;
        }
    }

}
